package 中等.位运算;

/**
 * 给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
 * 如果当前数字为偶数，则将其除以 2 。
 * 如果当前数字为奇数，则将其加上 1 。
 * 题目保证你总是可以按上述规则将测试用例变为 1 。
 */
public class 将二进制表示减到1的步骤数_1404 {

    public static void main(String[] args) {

        for (int i = 0; i < 5; i++) {
            System.out.println(Math.pow(2, i));
        }

        for (int i = 1; i < 30; i++) {
            System.out.println(Integer.toBinaryString(i));
            if (i % 2 == 0) {
                System.out.println("---");
            }
        }
        System.out.println(numSteps("1101"));

    }

    /**
     * 位运算+模拟+找规律
     * 1，如果是偶数，需要除以 2，位运算右移一位就行
     * 2，如果是奇数，右边的第一位是 1
     * 性质：2^0 + 2^1 + ... + 2^(i-1) = 2^i - 1
     * 分类讨论：
     * a. 类似 10111 +1 --> 11000，对于右侧连续的 1，将其左边第一个 0 变成 1
     * 右侧所有 1 变成 0
     * b. 全部为 1111 +1 --> 10000，原来的 1 全部变成 0，最左边加个 1
     */
    public static int numSteps(String s) {
        int ans = 0;
        StringBuilder builder = new StringBuilder(s);

        while (builder.length() != 1 || builder.charAt(0) != '1') {
            // 奇数
            if (builder.charAt(builder.length() - 1) == '1') {

                increment(builder);

                ans += 2;
            } else {
                ans++;
            }
            builder.deleteCharAt(builder.length() - 1);
        }

        return ans;
    }

    private static void increment(StringBuilder builder) {
        // 从右往左第一个 0 的索引，变成 1 ，其右侧的 1 变成 0
        int idx = -1;
        for (int i = builder.length() - 1; i >= 0; i--) {
            if (builder.charAt(i) == '0') {
                idx = i;
                builder.setCharAt(i, '1');
                break;
            }
            builder.setCharAt(i, '0');
        }
        if (idx == -1) {
            builder.insert(0, "1");
        }
    }

}
